package org.yege.algorithm.hash;
import java.util.*;

/**
 * 一致性hash算法（不带虚拟节点）
 */
public class ConsistentHash extends AbstractHash{
    private SortedMap<Integer,String> sortedMap=new TreeMap<Integer, String>();//真实服务器hash值和真实服务器对应关系的Map

    private Map<String,Long> serverNodeHasKeys=new HashMap<String, Long>();//真实服务器存储key的个数计数器

    public void addServerNode(String nodeName) {
        int serverNodeHashCode=fnv1_32_hash(nodeName);
        sortedMap.put(serverNodeHashCode,nodeName);
    }

    public void removeServerNode(String nodeName) {
        int serverNodeHashCode=fnv1_32_hash(nodeName);
        if(sortedMap.containsKey(serverNodeHashCode)){
            sortedMap.remove(serverNodeHashCode);
            serverNodeHasKeys.remove(nodeName);
        }
    }

    public String getServerNodeByKey(String key) {
        //得到该key的hash值
        int hash = fnv1_32_hash(key);
        //得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if(subMap.isEmpty()){
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = sortedMap.firstKey();
            //返回对应的服务器
            String serverNode=sortedMap.get(i);
            if(serverNodeHasKeys.containsKey(serverNode)){
                Long l=serverNodeHasKeys.get(serverNode);
                serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
            }else {
                serverNodeHasKeys.put(serverNode,Long.valueOf(1));
            }
            return serverNode;
        }else{
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            String serverNode=subMap.get(i);
            if(serverNodeHasKeys.containsKey(serverNode)){
                Long l=serverNodeHasKeys.get(serverNode);
                serverNodeHasKeys.put(serverNode,new Long(l.longValue()+1));
            }else {
                serverNodeHasKeys.put(serverNode,Long.valueOf(1));
            }
            return serverNode;
        }
    }

    /**
     * 计算服务器节点命中的标准差
     * @return
     */
    public double getStandardDeviation(){
        Set<String> servers=serverNodeHasKeys.keySet();
        for(String serverNode:servers){
            System.out.println("服务节点【"+serverNode+"】存储keys数量:"+serverNodeHasKeys.get(serverNode));
        }
        Collection<Long> longs =serverNodeHasKeys.values();
        Long[] array= new Long[longs.size()];
        longs.toArray(array);
        int sum = 0;
        for(int i=0;i<array.length;i++){
            sum += array[i];      //求出数组的总和
        }
        double average = sum/array.length;  //求出数组的平均数
        int total=0;
        for(int i=0;i<array.length;i++){
            total += (array[i]-average)*(array[i]-average);   //求出方差，如果要计算方差的话这一步就可以了
        }
        double standardDeviation = Math.sqrt(total/array.length);   //求出标准差
        return standardDeviation;
    }
}
